package practice.divingforgold;

import java.util.Scanner;

public class Main {

	//for solve single ONLY
	//Index [item][weightleft]
	int[][]solutions;
	
	//for solve multiple ONLY
	//Index [weightleft]
	int[]solutionm;
	
	//weight of each item.
	int[] weight;
	//value of each item.
	int[] value;
	
	//Special for diving for gold
	int w;
	
	/*
	 * NOTES:
	 * 		handle when num items = 0
	 */
	
	public Main() {
		Scanner s = new Scanner(System.in);
		boolean f=true;
		while (s.hasNext()){
			//Print a line between each case
			if(!f)
				System.out.println("");
			f=false;
			//Get the bounds...
			int maxWeight = s.nextInt();
			w = s.nextInt(); //Specific to diving for gold
			int numItems = s.nextInt();
			//Needed for all cases
			setupSingle(numItems,maxWeight);
			//Fill in weights and values
			for (int i =0; i < numItems; i++){
				weight[i]=s.nextInt()*w*3;
				value[i]=s.nextInt();
			}
			//Handle 0 case
			if (numItems==0){
				System.out.println("0\n0");
			}
			else{
				//Solve it, and print the max weight
				System.out.println(solveSingle());
				//Print the number of solutions
				System.out.println(getNumSolutionsSingle());
				//Print the weight and value of each item IN THE ORDER THEY WERE ADDED.
				printSolutionSingle();
			}
		}
	}
	/**
	 * Setup the arrays
	 * This is here so we don't accidently do this wrong (like getting an index wrong)
	 * ONLY USE FOR SOLVE SINGLE
	 * @param numItems	The total number of items.
	 * @param maxWeight The maximum possible weight
	 */
	public void setupSingle(int numItems, int maxWeight){
		
		solutions = new int[numItems][maxWeight+1];
		weight=new int[numItems];
		value=new int[numItems];
		
		for (int i=0;i<numItems;i++){
			for (int j=0;j<maxWeight+1;j++){
				solutions[i][j]=-1;
			}
		}
	}
	public int solveSingle(){
		return solveSingle(value.length-1,solutions[0].length-1);
	}
	/**
	 * ONLY WORKS FOR POSITIVE WEIGHTS
	 * ONLY ONE INTANCE OF EACH ITEM
	 * USES SOLUTIONS[][]
	 * 
	 * solution must be all -1's to start
	 * start with solve(num_items-1, total_weight)
	 * 
	 * @param item
	 * @param weightLeft
	 * @return
	 */
	public int solveSingle(int item, int weightLeft){
		if (item==-1)
			return 0;
		if (solutions[item][weightLeft]==-1){
			//Don't use item
			int valuewithout = solveSingle(item-1,weightLeft);
			//Use item
			int valuewith=0;
			
			if (weight[item]<=weightLeft)
				valuewith = value[item]+solveSingle(item-1, weightLeft-weight[item]);
			//Max
			solutions[item][weightLeft]=Math.max(valuewithout,valuewith);
		}
		return solutions[item][weightLeft];
	}
	/**
	 * Aux method for getNumSolutionsSingle(item,weightLeft)
	 * @return
	 */
	public int getNumSolutionsSingle(){
		return getNumSolutionsSingle(value.length-1,solutions[0].length-1);
	}
	/**
	 * Gets the numbers of items used in the solution.
	 * ONLY USE FOR SOLVE SINGLE
	 * 
	 * @param item The current item number (start from numitems-1)
	 * @param weightLeft The weight left (start from maxweight)
	 * @return The number of items used in solution
	 */
	public int getNumSolutionsSingle(int item, int weightLeft){
		if (item==0)
			return weight[0]<=weightLeft?1:0;
		
		if (weightLeft>=weight[item] && solutions[item][weightLeft]==value[item]+solutions[item-1][weightLeft-weight[item]])
			
			return getNumSolutionsSingle(item-1,weightLeft-weight[item])+1;
			
		return getNumSolutionsSingle(item-1,weightLeft);
	}
	/**
	 * Aux method for printSolutionSingle(item,weight)
	 */
	public void printSolutionSingle(){
		printSolutionSingle(value.length-1,solutions[0].length-1);
	}
	/**
	 * Prints the weight and value of each node used in solution
	 * @param item
	 * @param weightLeft
	 */
	public void printSolutionSingle(int item, int weightLeft){
		
		if (item==0){
			
			if (weight[0]<=weightLeft)
				//Needs to be changed based on situation
				System.out.println(weight[0]/3/w+" "+value[0]);
		
			return;
		}
		
		if (weightLeft>=weight[item] && solutions[item][weightLeft]==value[item]+solutions[item-1][weightLeft-weight[item]]){
			
			printSolutionSingle(item-1,weightLeft-weight[item]);
			//Changed based on situation
			System.out.println(weight[item]/3/w+" "+value[item]);
		}
		else
			printSolutionSingle(item-1,weightLeft);
	}
	/**
	 * ONLY WORKS FOR POSITIVE WEIGHTS
	 * MULTIPLE INTANCES OF EACH ITEM ALLOWED
	 * USES SOLUTIONM[]
	 * 
	 * solution must be all -1's to start
	 * start with solve(total_weight)
	 * 
	 * @param weightLeft
	 * @return
	 */
	public int solveMultiple(int weightLeft){
		if(solutionm[weightLeft]==-1){
			//without item.
			int valuewithout=solveMultiple(weightLeft-1);
			//with and item
			int valuewith=0;
			//Go through all items
			for (int i =0; i < value.length;i++){
				valuewith = Math.max(valuewith, value[i]+solveMultiple(weightLeft-weight[i]));
			}
			solutionm[weightLeft] = Math.max(valuewithout, valuewith);
		}
		return solutionm[weightLeft];
	}
	
	public static void main(String[] args) {
		new Main();
	}

}
